Batch 2 - Class 277 - Divisor Game
Zoom: send meeting Id and password
Start recording
Preclass Exercise:
Gulab Jamuns
- An school canteen sells two gulab jamuns for Rs 12 in a bowl, such that the perfectly spherical gulab jamuns fill the bowl. A shop outside the school introduces a new offering to sell three gulab jamuns for Rs 15 in a bowl of same size, so that the perfectly spherical gulab jamuns fill the bowl. Kids are excited at getting gulab jamuns at Rs 5 per piece rather than Rs 6 per piece! But is this a good strategy on part of the new shop?
Answer: The approach is to calculate the volume of gulab jamuns in each bowl. It turns out that the second bowl has 20% more volume than the first, but is priced 25% higher. So the shop keeper actually makes more profit per bowl. Customer of course are happy to get gulab jamuns at lower price per piece.Instructor Notes: Since kids may not know trigonometry, let them come up with the approach, and then one may suggest that the volume of the smaller gulab jamun is about 80% of the volume of the larger ones
Attendance: Raghav, Aneesh, Kabir, Advay, Shikhar, Ayush, Rhea Chadha, Ryan Chadha, Rohan, Siddanth, Yatharth, Dhriti, Anika, Vansh, Adyant, Kkushagra, Siddharth, Ishita, Aarkin
Class Notes:
Divisor Game (Repeat from class 80)
To play the divisor game, choose a number N and list all its positive divisors including 1 and N. Two players take turns crossing out a number from that list. Each time they cross out a number, they must cross out all its divisors. Whoever crosses out N is the loser of the game.
Let kids play some of the games.
- Help organize - how should we draw the divisors and arrange them, so that crossing out is easier?
- Lets take some simple cases. For example, product of two primes.
- Do all these games have the same outcomes?
- Why? Does the outcome depend on the numbers or something else? Patterns?
- What about product of 3 primes?
- Generalize using Strauss' analysis with product of primes, and mapping to Pascal's triangle
- Take another pattern - an exponent of a prime number, and see what happens
- (A^x)B where A and B are primes? (Strauss' example with 12)
- Can we classify some patterns as winning patterns for the first person?
- List down some of the patterns that are winning patterns for the first person
- Can someone find a losing pattern for the first person?
- (Teacher's Note: Make sure kids understand what is a "Losing Position" - its a position from where regardless of the move the person makes, she will lose - i.e. all moves take to winning positions). By contrast, "Winning Positions" are positions from where there exists a move to a losing position - i.e. there is at least one move to a losing position)
- Answer: 6 connected to 2 and 3 (no connecting 1, which has been taken out). Or a 12-4-2 and 12-6-3
- Note that all cases where there is a "corresponding move" on another leg qualify for this
- How can any number be written in terms of patterns?
- Think prime factorizations
- Do you think the first player can always win?
- Any ideas why?
- Teacher's Note: If kids can get to the strategy stealing argument, great. Else given them a sense of it
- There were some patterns where first person lost - why do those not show up?
- Lets try one "losing pattern" and see how we can avoid getting there in the simplest case.
- Thinking from the first person standpoint, can he leave the second person with one of these losing patterns? (again in simplest cases)
- There seems to be a mapping of this problem to NIM games with n piles, the size of piles being the exponents of the n prime numbers in factorization of N, or perhaps the lengths of longest paths on each leg. However, the cross-connections make the mapping harder. You would then want to leave the opponent with even nim-sum (not counting the top main number, because here the person who take that loses, unlike in NIM games).
Homework Problem:
- Think about the solution to "how" of Divisor problem
References: